{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "google",
   "metadata": {},
   "source": [
    "##### Copyright 2023 Google LLC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "apache",
   "metadata": {},
   "source": [
    "Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "basename",
   "metadata": {},
   "source": [
    "# quasigroup_completion"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "link",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "<td>\n",
    "<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/contrib/quasigroup_completion.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
    "</td>\n",
    "<td>\n",
    "<a href=\"https://github.com/google/or-tools/blob/main/examples/contrib/quasigroup_completion.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
    "</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "doc",
   "metadata": {},
   "source": [
    "First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "install",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install ortools"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "description",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "  Quasigroup completion Google CP Solver.\n",
    "\n",
    "\n",
    "  See Carla P. Gomes and David Shmoys:\n",
    "  \"Completing Quasigroups or Latin Squares: Structured Graph Coloring Problem\"\n",
    "\n",
    "  See also\n",
    "  Ivars Peterson \"Completing Latin Squares\"\n",
    "  http://www.maa.org/mathland/mathtrek_5_8_00.html\n",
    "  '''\n",
    "    Using only the numbers 1, 2, 3, and 4, arrange four sets of these numbers\n",
    "    into\n",
    "    a four-by-four array so that no column or row contains the same two numbers.\n",
    "    The result is known as a Latin square.\n",
    "    ...\n",
    "    The so-called quasigroup completion problem concerns a table that is\n",
    "    correctly\n",
    "    but only partially filled in. The question is whether the remaining blanks\n",
    "    in\n",
    "    the table can be filled in to obtain a complete Latin square (or a proper\n",
    "    quasigroup multiplication table).\n",
    "    '''\n",
    "\n",
    "    Compare with the following models:\n",
    "    * Choco: http://www.hakank.org/choco/QuasigroupCompletion.java\n",
    "    * Comet: http://www.hakank.org/comet/quasigroup_completion.co\n",
    "    * ECLiPSE: http://www.hakank.org/eclipse/quasigroup_completion.ecl\n",
    "    * Gecode: http://www.hakank.org/gecode/quasigroup_completion.cpp\n",
    "    * Gecode/R: http://www.hakank.org/gecode_r/quasigroup_completion.rb\n",
    "    * JaCoP: http://www.hakank.org/JaCoP/QuasigroupCompletion.java\n",
    "    * MiniZinc: http://www.hakank.org/minizinc/quasigroup_completion.mzn\n",
    "    * Tailor/Essence': http://www.hakank.org/tailor/quasigroup_completion.eprime\n",
    "    * SICStus: http://hakank.org/sicstus/quasigroup_completion.pl\n",
    "    * Zinc: http://hakank.org/minizinc/quasigroup_completion.zinc\n",
    "\n",
    "  This model was created by Hakan Kjellerstrand (hakank@gmail.com)\n",
    "  Also see my other Google CP Solver models:\n",
    "  http://www.hakank.org/google_or_tools/\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "code",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "from ortools.constraint_solver import pywrapcp\n",
    "\n",
    "default_n = 5\n",
    "X = 0\n",
    "# default problem\n",
    "# (This is the same as quasigroup1.txt)\n",
    "default_puzzle = [[1, X, X, X, 4], [X, 5, X, X, X], [4, X, X, 2, X],\n",
    "                  [X, 4, X, X, X], [X, X, 5, X, 1]]\n",
    "\n",
    "\n",
    "def main(puzzle=\"\", n=0):\n",
    "\n",
    "  # Create the solver.\n",
    "  solver = pywrapcp.Solver(\"Quasigroup completion\")\n",
    "\n",
    "  #\n",
    "  # data\n",
    "  #\n",
    "\n",
    "  if puzzle == \"\":\n",
    "    puzzle = default_puzzle\n",
    "    n = default_n\n",
    "\n",
    "  print(\"Problem:\")\n",
    "  print_game(puzzle, n, n)\n",
    "\n",
    "  # declare variables\n",
    "  x = {}\n",
    "  for i in range(n):\n",
    "    for j in range(n):\n",
    "      x[(i, j)] = solver.IntVar(1, n, \"x %i %i\" % (i, j))\n",
    "\n",
    "  xflat = [x[(i, j)] for i in range(n) for j in range(n)]\n",
    "\n",
    "  #\n",
    "  # constraints\n",
    "  #\n",
    "\n",
    "  #\n",
    "  # set the clues\n",
    "  #\n",
    "  for i in range(n):\n",
    "    for j in range(n):\n",
    "      if puzzle[i][j] > X:\n",
    "        solver.Add(x[i, j] == puzzle[i][j])\n",
    "\n",
    "  #\n",
    "  # rows and columns must be different\n",
    "  #\n",
    "  for i in range(n):\n",
    "    solver.Add(solver.AllDifferent([x[i, j] for j in range(n)]))\n",
    "    solver.Add(solver.AllDifferent([x[j, i] for j in range(n)]))\n",
    "\n",
    "  #\n",
    "  # solution and search\n",
    "  #\n",
    "  solution = solver.Assignment()\n",
    "  solution.Add(xflat)\n",
    "\n",
    "  # This version prints out the solution directly, and\n",
    "  # don't collect them as solver.FirstSolutionCollector(solution) do\n",
    "  # (db: DecisionBuilder)\n",
    "  db = solver.Phase(xflat, solver.INT_VAR_SIMPLE, solver.ASSIGN_MIN_VALUE)\n",
    "\n",
    "  solver.NewSearch(db)\n",
    "  num_solutions = 0\n",
    "  while solver.NextSolution():\n",
    "    num_solutions += 1\n",
    "    print(\"Solution %i\" % num_solutions)\n",
    "    xval = [x[(i, j)].Value() for i in range(n) for j in range(n)]\n",
    "    for i in range(n):\n",
    "      for j in range(n):\n",
    "        print(xval[i * n + j], end=\" \")\n",
    "      print()\n",
    "    print()\n",
    "  solver.EndSearch()\n",
    "\n",
    "  if num_solutions == 0:\n",
    "    print(\"No solutions found\")\n",
    "\n",
    "  # # Note: AllSolution may take very much RAM, hence I choose to\n",
    "  # # show just the first solution.\n",
    "  # # collector = solver.AllSolutionCollector(solution)\n",
    "  # collector = solver.FirstSolutionCollector(solution)\n",
    "  # solver.Solve(solver.Phase([x[(i,j)] for i in range(n) for j in range(n)],\n",
    "  #                           solver.CHOOSE_FIRST_UNBOUND,\n",
    "  #                           solver.ASSIGN_MIN_VALUE),\n",
    "  #                           [collector])\n",
    "  #\n",
    "  # num_solutions = collector.SolutionCount()\n",
    "  # print \"\\nnum_solutions: \", num_solutions\n",
    "  # if num_solutions > 0:\n",
    "  #     print \"\\nJust showing the first solution...\"\n",
    "  #     for s in range(num_solutions):\n",
    "  #         xval = [collector.Value(s, x[(i,j)]) for i in range(n) for j in range(n)]\n",
    "  #         for i in range(n):\n",
    "  #             for j in range(n):\n",
    "  #                 print xval[i*n+j],\n",
    "  #             print\n",
    "  #         print\n",
    "\n",
    "  print()\n",
    "  print(\"num_solutions:\", num_solutions)\n",
    "  print(\"failures:\", solver.Failures())\n",
    "  print(\"branches:\", solver.Branches())\n",
    "  print(\"WallTime:\", solver.WallTime())\n",
    "\n",
    "\n",
    "#\n",
    "# Read a problem instance from a file\n",
    "#\n",
    "def read_problem(file):\n",
    "  f = open(file, \"r\")\n",
    "  n = int(f.readline())\n",
    "  game = []\n",
    "  for i in range(n):\n",
    "    x = f.readline()\n",
    "    row_x = (x.rstrip()).split(\" \")\n",
    "    row = [0] * n\n",
    "    for j in range(n):\n",
    "      if row_x[j] == \".\":\n",
    "        tmp = 0\n",
    "      else:\n",
    "        tmp = int(row_x[j])\n",
    "      row[j] = tmp\n",
    "    game.append(row)\n",
    "  return [game, n]\n",
    "\n",
    "\n",
    "def print_board(x, rows, cols):\n",
    "  for i in range(rows):\n",
    "    for j in range(cols):\n",
    "      print(\"% 2s\" % x[i, j], end=\" \")\n",
    "    print(\"\")\n",
    "\n",
    "\n",
    "def print_game(game, rows, cols):\n",
    "  for i in range(rows):\n",
    "    for j in range(cols):\n",
    "      print(\"% 2s\" % game[i][j], end=\" \")\n",
    "    print(\"\")\n",
    "\n",
    "\n",
    "\n",
    "if len(sys.argv) > 1:\n",
    "  file = sys.argv[1]\n",
    "  print(\"Problem instance from\", file)\n",
    "  [game, n] = read_problem(file)\n",
    "  main(game, n)\n",
    "else:\n",
    "  main()\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 5
}
